#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;

#define in read()
#define pii pair<int,int>
#define fi first
#define se second
#define FILE(x) freopen(x".in","r",stdin);\
	freopen(x".out","w",stdout);
#define pb push_back

int read(){
	int x = 0,sgn = 1;char ch = getchar();
	for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = -1;
	for(;isdigit(ch);ch = getchar()) x = (x<<1)+(x<<3)+(ch^48);
	return x*sgn;
}

const int N = 1e5+10;

int n,Q,a[N],b[N],tot,cnt,BL,bl[N],bn;
ll tong[N],ans[N];

struct query{int l,r,id;}q[N];
bool operator < (query a,query b){return bl[a.l] ^ bl[b.l] ? bl[a.l] < bl[b.l] : a.r < b.r;}

ll calc(int l,int r){
	static ll cc[N]; ll res = 0; for(int i = l;i <= r;i++) cc[a[i]] = 0;
	for(int i = l;i <= r;i++) cc[a[i]] += b[a[i]],res = max(res,cc[a[i]]);
	return res;
}

int main (){
#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
#endif
	n = in,Q = in; BL = sqrt(n);
	for(int i = 1;i <= n;i++) a[i] = b[i] = in,bl[i] = (i - 1) / BL + 1; bn = bl[n];
	for(int i = 1;i <= Q;i++) q[i].l = in,q[i].r = in,q[i].id = i;
	sort(q+1,q+Q+1); sort(b+1,b+n+1); tot = unique(b+1,b+n+1) - b - 1;
	for(int i = 1;i <= n;i++) a[i] = lower_bound(b+1,b+tot+1,a[i]) - b;
	for(int i = 1,j = 1;j <= bn;j++){
		int br = min(j * BL,n),l = br + 1,r = l - 1;ll tot = 0;
		for(;bl[q[i].l] == j;i++){
			if(bl[q[i].r] == j) ans[q[i].id] = calc(q[i].l,q[i].r);
			else{
				while(r < q[i].r){
					++r; tong[a[r]] += b[a[r]];
					tot = max(tot,tong[a[r]]);
				}
				ll tt = tot;
				while(l > q[i].l){
					--l; tong[a[l]] += b[a[l]];
					tot = max(tot,tong[a[l]]);
				}
				ans[q[i].id] = tot;
				while(l <= br){tong[a[l]] -= b[a[l]]; ++l;}
				tot = tt;
			}
		}
		memset(tong,0,sizeof(tong));
	}
	for(int i = 1;i <= Q;i++) printf("%lld\n",ans[i]);
	return 0;
}
